//
//  main.c
//  Questions
//
//  Created by wangrui.
//  Copyright (c) 2014年 wangrui. All rights reserved.
//

/*
 *数组方式构造树
 *建立最小堆，及插入、删除元素
 *堆排序
 *2014-09-29 10:31:13
 *测试数据:(14个) 99 5 36 7 22 17 46 12 2 19 25 28 1 92
 */

#include <stdio.h>
#include <stdlib.h>
#include "cutils.h"

#define MaxNodes 100

void siftdown(int tree[], int idx,int n) {
	int t,flag = 0;
	
	while (idx*2 <= n && flag == 0) {
		
		if (tree[idx] > tree[2*idx]) {
			t = 2 * idx;
		}
		else {
			t = idx;
		}
		
		if (2*idx + 1 <= n) { //有右节点
			if (tree[t] > tree[2*idx+1]) { //要对比左子树和右子树的大小
				t = 2*idx + 1;
			}
		}
		
		if (t != idx) {
			swap(&tree[idx], &tree[t]);
			idx = t;
		}
		else{
			flag = 1;
		}
	}
	
}

void siftup(int tree[],int idx) {
	int flag = 0;
	while (idx != 1 && flag == 0) {//非堆顶
		if(tree[idx] < tree[idx/2]){
			swap(&tree[idx], &tree[idx/2]);
		}
		else{
			flag = 1 ;
		}
		
		idx /= 2;
	}
}

void insert(int tree[], int value, int *num) {
	*num = *num + 1;
	tree[*num] = value;
	siftup(tree, *num);
}

/*
 *如果要删任意的元素,则要进行数组的删除，再重新建堆
 */
int deleteTop(int tree[],int *num) {
	
	int temp = tree[1];
	
	tree[1] = tree[*num];
	*num = *num - 1; //这行代码非常重要
	siftdown(tree, 1, *num); //调整堆顶
	
	return temp;
}

void heapAdjust(int tree[], int n) {
	for (int i = n/2; i>=1; i--) {
		siftdown(tree, i, n);
	}
}

/*
 * 跟删除堆顶的思想一样，堆顶的肯定是最小的
 */
void heapSort(int tree[], int num) {
	
	int t = num;
	
	while (t > 1) {
		swap(&tree[1], &tree[t]);
		t--;
		siftdown(tree, 1, t);
	}

}

int main(int argc, const char * argv[])
{
	int num;
	scanf("%d",&num);
	
	int tree[MaxNodes];
	for (int i=1; i<=num; i++) {
		scanf("%d",&tree[i]);
	}
	
	heapAdjust(tree,num);
	printArray(tree+1, num);
	
	insert(tree, 88, &num);
	printArray(tree+1, num);
	
	deleteTop(tree, &num);
	printArray(tree+1, num);
	
	heapSort(tree, num);
	printArray(tree+1, num);
	
	return 0;
}


